package offer;

public class EX12 {
    boolean [][] flag;
    int down;
    int right;

    public boolean exist(char[][] board, String word) {
        if(board.length<=0){
            return false;
        }
        down = board.length;
        right = board[0].length;
        flag = new boolean[down][right];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(help(board,word,1,i,j)){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean help(char[][] board,String word,int len,int i ,int j){
        if(i<0||j<0||i>=down||j>=right|| flag[i][j]){
            return false;
        }
        if(word.length()==len){
            if(word.charAt(len-1)==board[i][j]){
                return true;
            }else{
                return false;
            }
        }
        if(word.charAt(len-1)==board[i][j]){
            flag[i][j] = true;
            boolean abs =help(board,word,len+1,i,j+1)||
                    help(board,word,len+1,i,j-1)||
                    help(board,word,len+1,i+1,j)||
                    help(board,word,len+1,i-1,j);
            flag[i][j] = false;
            return abs;
        }else{
            return false;
        }

    }

    public static void main(String[] args) {
        EX12 ex12 = new EX12();
        char[][] board = {{'C','A','A'},{'A','A','A'},{'B','C','D'}};
        String word = "AAB";
        ex12.exist(board,word);
    }


}
